/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <p>
 * 给定一个正整数数组和整数值，求得所有整数数组值等于目标值的所有组合 该整数数组的所有元素最多只能使用一次。
 * 
 * For example, 
 * given candidate set 10,1,2,7,6,1,5 and target 8, 
 * A solution set is: 
 * [1, 7] [1, 2, 5]
 * [2, 6] [1, 1, 6]
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com 2015年5月24日
 */
public class CombinationSumII {

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        //边界判断
        if(candidates==null || target<0){
            return result;
        }
        Arrays.sort(candidates);
        int len = candidates.length;
        //非正数判断
        if(candidates[0]<0 || candidates[len-1]<0){
            return result;
        }
        
        List<Integer> path = new ArrayList<Integer>();
        //查找组合和满足第一个元素里面的每个元素只出现一次
        findCombinationSum2(candidates,0,target,path,result);
        return result;
    }

    /**
     * 查找目标和
     * 
     * @param candidates
     * @param start
     * @param target
     * @param path
     * @param result
     * @author towan 2015年5月24日
     */
    private void findCombinationSum2(int[] candidates, int start, int target, List<Integer> path,
            List<List<Integer>> result) {
        // 判断目标值
        if (target < 0) {
            return;
        }
        //找到对应的元素
        if(target==0){
            result.add(new ArrayList<Integer>(path));
        }else{
            for(int i = start;i<candidates.length;i++){
                if(candidates[i]>target){
                    break;//
                }else{
                    //避免重复加入,序列含有相同的元素，那怕每个元素使用一次，也可能出现重复组合，只取第一个相同值加入到结果中 
                    if(i!=start && candidates[i]==candidates[i-1]){
                        continue;
                    }
                    path.add(candidates[i]);
                    //下次递归不能从当前位置开始
                    findCombinationSum2(candidates, i+1, target-candidates[i], path, result);
                    // FIXME 重置
                    path.remove(path.size()-1);
                    
                }
            }
        }
    }
}
